\section{Class-Based Matching}


%\textbf{Class-Based Matching.} 
 
%\subsection{The problem}
%
%Given the source instances $S$ and their candidate instances $C$, class-based matching  is the problem of finding the correct matches $M(s)$ to $s \in S$ when $s \in S$ and $t \in C$ share insufficient features for reliable direct matching. The  information  considered to find   matches $M(s)$   is therefore only the features of the  candidate instances  $t \in C$. 
%
%Particularly, class-based matching is build upon the observation that matching is performed for a class of source instances. That is, all $s \in S$ belong to a specific class\footnote{Notice that when the input $S$ captures different classes, it can be partitioned into sets of instances representing specific classes \cite{typifier}.}.  Our assumption is that if $S$ is a class (its members share common features), then the set of correct matches   for $s \in S$ should also belong to a class, i.e., the correct target   matches $M^*= \{t | t \in M(s) \in M(S) \}$ should also share some common features among themselves. 
 %
%Using this assumption, the challenge of finding $M^*$ can be solved by finding the subset $M \subseteq C$ that forms the most concise class, i.e.\ where the similarities of the instances in $M$ are maximized, or, in the optimal case, $M=M^*$.  
%
%Class-based matching does not directly compare $s \in S$ with a candidate $t \in C$. Rather, it determines whether $t$ is a match or not based on its class membership, i.e. whether it ``belongs to'' $M^*$. Here, $M^*$ acts as an idealized instance-based representation of the target class of interest. In practice, $M^*$ is not given but stands for the actual result to be determined by instance matching. 
%
%
%In the current example, the instance in the set $M_1=$ \{\verb+db:Belmont_California+, \verb+db:San_Francisco+ and \verb+db:San_Jose_+\verb+California+\}  are more similar to each other than those from the set $M_2=$ \{\verb+db:Belmont_France+, \verb+db:San_Francisco+  and \verb+db:San_Jose_+\verb+California+\}. We say, therefore, $M_1$  is a more concise class than $M_2$. Precisely,  the candidate \verb+db:Belmont_California+ shares the predicate \verb+db:country+ and value \verb+db:Usa+ with the instance \verb+db:San_Francisco+, which shares the predicate \verb+db:locatedIn+ and value \verb+db:California+ with the instance \verb+db:San_Jose_+\verb+California+. Consequently, class-based matching would consider   $M_1$ as more likely to contain the correct matches for the source instances than $M_2$.


Let $S$ be the instances from the source dataset and $M^*$ be the ground truth, containing all and only correct matches in the target dataset. The candidate instances $C$ computed via direct matching might   be not sound and not complete, i.e. there is a candidate in $C$ that is not in $M^*$ and there is a an element in $M^*$ that is not in $C$, when some $s \in S$ and corresponding elements $t \in C$ only have few features that directly match. Class-based matching aims to find those non-sound matches in C (to improve soundness / precision), using only features of the candidate instances $t \in C$. 

Particularly, CBM is built upon the observation that matching is usually performed for a class of source instances. That is, all $s \in S$ belong to a specific class\footnote{Notice that when the input $S$ captures different classes, it can be partitioned into sets of instances representing specific classes \cite{typifier}.}.  Our idea is that if $S$ is a class, i.e., its instances share some features, then correct matches for $s \in S$ should also belong to a class, i.e., instances in $M^*$
%= \{t | t \in M(s) \in M(S) \}$ 
should also share some common features. Then, we aim to compute $M^*$ by finding a subset $M \subseteq C$, whose instances are most similar to each other (compared to other candidate subsets). These instances are considered \emph{class-based matches} because they form a class that matches the class of interest. 

%Consequently, class-based matching tries to find $M^*(S)$ from the candidates $t \in C(s) \in C(S)$.

%More precisely, class-based matching tries to find the set that  uses an approximation of this class because $M^*(S)$ is not given but stands for the actual result to be determined by instance matching. In this way, only information from the target is used for matching, namely the candidates $t \in C(s) \in C(S)$ and the CoI $M^*(S)$ captured as subsets of these candidates. 



%Let $M^*(S)$ be the optimal result that contains only correct matches for every $s \in S$. Class-based matching does not directly compare $s$ with a candidate $t \in C(s)$. Rather, it determines whether $t$ is a match or not based on its class membership, i.e. whether it ``belongs to'' $M^*(S)$, which acts as an instance-based representation of the class of interest (CoI). More precisely, it uses an approximation of this class because $M^*(S)$ is not given but stands for the actual result to be determined by instance matching. In this way, only information from the target is used for matching, namely the candidates $t \in C(s) \in C(S)$ and the CoI $M^*(S)$ captured as subsets of these candidates. 


%For example, consider a set of source instances $S$  of the type \verb+Drug+. Class-based matching exploits the intuition that correct matches in the target must belong to a class that corresponds to \verb+Drug+, e.g. \verb+Medication+. However, our previous study of heterogeneous data shows that class information is often missing or might be too general to be useful \cite{typifier}. That is, the class to which $t$ (or $s$) belongs to might not be explicitly given in the target (source); or the class to which $t$ belongs is specific (e.g. \verb+Medication+) while the one $s$ belong to is much more general (e.g \verb+Product+). Hence, classes might be missing or too different in granularity such that a direct matching at the class-level is not always possible.

%Addressing this, class-based matching employs a latent, \emph{instance-based representation} of the class that is determined during the instance matching process. In this example, we would need a representation for the class \verb+Medication+, for which we employ an approximation of $M^*(S)$ that shall capture all instances of the type \verb+Medication+. Because the matching is non-direct, the class   which $s$ belongs to is not needed but the candidates $t \in C(s) \in C(S)$ and $M^*(S)$. The problem is how to obtain a good approximation that captures all instances of the CoI, which coincides with the actual problem of instance matching, i.e. finding the optimal results $M^*(S)$. 

\subsection{Formal Definition} 
%The class-based matching problem is a particular case of clustering, where we want to separate the set of candidate matches $C = \bigcup_{\forall s\in S: C(s) \in C(S)} C(s)$ in two clusters, namely $M$ and $M^-$, which contain the matches and non-matches of $S$, respectively, and for all $s\in S$, we want to identify $M(s)$, where $M = \bigcup_{\forall s\in S: M(s) \subseteq C(s)} M(s)$ and $M(s) \neq \emptyset$. 

%The class-based matching can be  seem as a particular case of clustering, where the candidates $C$ are separated into the matches $M$ and the non-matches $M^-$.  It resembles a clustering problem because it is an unsupervised approach for separating the data spaces (i.e.\ the candidates $C$) but it is substantially different from clustering techniques (e.g.\ k-means). 

%First, class-based matching focus on finding the set $M$.  It means that   traditional clustering approaches are not sufficient because even if it could separate $C$ in two clusters, we would still have the problem of deciding which one is $M$ between the two clusters. 

%Second,  we assume there is exactly one match for $s \in S$. This adds the additional constraint to the problem, not required in the traditional clustering settings, that  $\forall s\in S: |M(s)| = 1$, assuming $C(s) \neq \emptyset$. Notice that in verifying this constraint equates in computing  $M(s) = C(s) \cap M$, i.e.\ it consists of mapping the correct matches to their corresponding source instances. Therefore, if we can find $M$, we solve the problem of finding $M(S)$, as well. Given $M$ and $C(s) \in C(S)$, this particular problem of computing $M \cap C(s)$ for all $s \in S$ can be solved in $O(ln |M|)$ \cite{Vazirani:2001:AA:500776}. 

For the sake of presentation, we formalize the basic version of our problem first: assuming individual datasets contain no duplicates, such that for each source instance, the goal is to find exactly one match in the target dataset, i.e. $|M|=|S|$ with $|M(s)| = 1$, for all $s \in S$. Then, the CBM problem can be formulated as follows:

%\begin{definition}[CoI, Class-based Matching]  To find the best representation for the CoI and solution for the class-based matching problem, respectively, consists of computing
\begin{definition}[Class-based Matching (CBM)]  The solution for the class-based matching problem can be computed as 
\begin{equation}
\footnotesize
\begin{aligned}
&  M^* \approx \argmax_{M  \in \mathbf{M}} \frac{\sum_{t \in M} Sim(t, M)}{|M|} \\
& \text{Subject to:} \\
&  \forall s \in S:  |C(s) \cap M| = |M(s)| = 1 
\end{aligned}
\label{eq:opt}
\end{equation}
% &   Sim(t, M)  > \delta  \text{ and } \\

where  $\mathbf{M}$ is the set containing all possible candidate subsets $M$ as elements, 
%The term $Sim(t, M)  > \delta$ captures the heuristic that avoids non-matches, i.e.\ focuses only on finding $M$. 
$Sim(t, M)$ is a function that returns the similarity between an instance $t$ and the subset of candidates $M$. %and  $\delta$ is a similarity threshold

%\DTR{i remove this because it just looks confusing at this place and is not really needed to capture the problem:}
%Note that $\sum_{t \in M} Sim(t, M)$ is equal to: 
%\begin{equation}
%\footnotesize
%\frac{1}{2} \sum_{t_i \in M}\sum_{t_j \in M} sim(t_i, t_j)  -  \sum_{t_i \in M}sim(t_i, t_i)\\
  %\label{eq:quadratic}
%\end{equation}
\end{definition}

%It requires to compute the similarity matrix $|M| \times |M|$ among the candidates instance. which in the worse case (when M = C) is bound by $O(|C|^2)$.
%Note that $Sim(t, M)$ operates over \textit{features} extracted from the instance $t$ and instances in the sets in $M$. This will be detail further, in our proposed solution to this problem.

%. However, we have empirically verified the CBM assumption for the problem of instance matching. The results (F1 measures) presented in the paper show that by solving CBM using an efficient approximated method proposed in Sec. \ref{sec:cbmsolution}, we obtain a set $M$ that approximates a  given ground truth $M^*$ with sufficient accuracy.

As an approximation for $M^* \in \mathbf{M}$, we compute a subset of candidate $M$ containing instances that are similar to itself, i.e. the goal is to maximize $Sim(t, M)$ for all $t \in M$. Compared to all other possible candidate subsets, the solution is the one that is most similar to its instances. Further, in this basic setting, it contains exactly one candidate for every source instance. 

As an example, we have as candidate subsets $M_1=$ \{\verb+db:Belmont_California+, \verb+db:San_Francisco+ and \verb+db:San_Jose_+\verb+California+\}  and $M_2=$ \{\verb+db:Belmont_France+, \verb+db:San_Francisco+  and \verb+db:San_Jose_+\verb+California+\} for the data in our scenario.  Instances in $M_1$
are more similar to $M_1$ than instances in $M_2$ are similar to $M_2$. In other words, the similarity among instances in $M_1$ is higher than the similarity among instances in $M_2$: the candidate \verb+db:Belmont_California+ shares the predicate \verb+db:country+ and value \verb+db:Usa+ with the instance \verb+db:San_Francisco+, which in turn, shares the predicate \verb+db:locatedIn+ and value \verb+db:California+ with \verb+db:San_Jose_+\verb+California+. Thus, CBM considers  $M_1$ as a better approximation of $M^*$ than $M_2$.

We note that typically, instance matching approaches do not provide a theoretically sound and complete solution. As captured above, CBM is also only an approximate solution in that sense. The quality of this approximation taken by our approach is studied in experiments using real-world matching tasks and datasets. 

%That is, $M^*$ is not only the result but at the same time, acts as the class that is compared with the candidates instances $t \in C$. 


\textbf{Computational Complexity.} The following theorem captures the complexity of this problem: 

\begin{theorem}
 CBM is an instance of  the \textit{maximum edge-weighted clique problem (MEWCP)} \cite{DBLP:journals/eor/AlidaeeGKW07}, therefore CBM is NP-hard.  
 
 
\end{theorem}

 

\begin{proof} Each candidate $t \in C$ can be mapped to a vertex in an undirected graph $G$. Two vertices $x, y \in C$ are connected if and only if $x \in C(s_i)$ and $y \in C(s_j)$, where $s_i \neq s_j$.  The weight of an edge $\{x, y\}$ is given by $sim(x,y)$.  Any clique in $G$ contains exactly one candidate for each $C(s) \in C(S)$. Then, a solution to the CBM problem is a clique in $G$ with maximum weight.   
\end{proof}


%Notice that the CBM is the formulation of a heuristic that approximates the true set of matches for $S$. In reality, the optimal solution for CBM may differ from the true set of matches $M^*$.  However, we have empirically verified the CBM assumption for the problem of instance matching. The results (F1 measures) presented in the paper show that by solving CBM using an efficient approximated method proposed in Sec. \ref{sec:cbmsolution}, we obtain a set $M$ that approximates a  given ground truth $M^*$ with sufficient accuracy.


%The goal of the paper is to find the matches for $S$ and compare it to state-of-the-art instance matching approaches. 

%Solving this problem requires  enumerating of all possible sets $\mathbf{M}$ and determining the optimal $M^*$. Since this enumeration could be very large, i.e., $|\mathbf{M}|=2^C$, we propose an approximate solution to this that does not require a full enumeration. Also, we show how to obtain a more compact representation of $M^*$. 

\textbf{CBM Variations.} Apart from the introduced basic setting, two other variants exist: \textit{1-to-many class-based matching  (1-to-many CBM)} and \textit{unrestricted class-based matching (UCBM)}. The former assumes $\forall s \in S: |M(s)| > 0$, while the latter, assumes $\forall s \in S: |M(s)| \geq 0$. 1-to-many CBM considers the cases where there is at least one match for each source instance, while UCBM considers the cases where some candidate set $C(s)$ may not contain a match to $s \in S$. To capture the UCBM problem, the constrain should be removed and the term


\begin{equation}
Z = \frac{\frac{\sum_{s\in S} |C(s) \cap M|}{|C(s)|}}{|S|}
\end{equation}

should be added to Eq.\ \ref{eq:opt}. $Z$ is simply an auxiliary term introduced to deal with the general case where $|M(s)|=|C(s) \cap M|$ might be zero. It helps to assign a solution set  $M \in \mathbf{M}$ a higher score, when the majority of its matches $M(s)$ has cardinality higher than zero; hence, it avoids solution sets with many empty matches. 
%This term is not needed in the setting where there always exists at least one candidate for a given source instance $s$. In this case, we can simplify Eq.\ \ref{eq:opt} removing $Z(S)$ and adding the constraint that $|M(s)|>0$.
%instance assume that the matches are one-to-one match or one-to-many, we can constrain $|M(s)|=1$, or $|M(s)|>0$, respectively. In those cases, 

%\begin{equation}
%\begin{aligned}
%& M^*(S) \approx \argmax_{M(S) \in \mathbf{M}} \frac{\sum_{M(s) \in M(S)} \sum_{t \in M(s)} Sim(t, M(S))}{\sum_{M(s) \in M(S)} |M(s)|}   %\\
%& \text{Subject to:} \\
%&Sim(t, M(S))  > \delta, \\
%& |M(s)|>0  \text{ and } \\
%& M(S)=\{M(s) |  s \in S : M(s) \subseteq C(s) \in C(S)\}
%\end{aligned}
%\label{eq:opt2}
%\end{equation}
  
In the next section, we propose an approach to solve CBM and its variants, 1-to-many CBM and UCBM.

% To compute the matches $M$ more efficiently, when the candidates would form a graph with thousands of nodes, we propose an  approximated solution to the CBM. We discuss this approach on Sec. 5.   


%\textbf{Class-Based Matching.} The direct matching paradigm has proven to be useful in the homogeneous setting where instances share some common predicates $p$. In the heterogeneous setting, we showed above that this paradigm would require some pairs of comparable predicates. Since these direct overlaps at the level of predicates (or values) between instances may do not exist, or are too few to perform matching in the heterogeneous setting, we propose class-based matching. This matching can be applied on top of candidate selection, or after a refined matching step based on direct matching as discussed.  The result of either of these two steps can be conceived as a set of candidates, $C(s)$, which is further refined by class-based matching to obtain $M(s)$.  
%
%\begin{definition} Candidate Set - Let S and T be the set of source and target data. A candidate set $C(s)$ for $s \in S$, is defined  as: $C(s) = \{t | \alpha >  Sim(s,t) < \delta \}$.
%\end{definition}
%

%Class-based matching does not directly compare $s$ with a candidate $t \in C(s)$. It determines whether $t$ is a match or not based on its class membership, which is derived using information in the target, namely the candidate sets $C(S) = \{C(s) | s \in S \}$. This matching builds upon the observation that matching is performed for a class of instances. That is, all $s \in S$ belongs to a specific class, called the class of interest (even when the input $S$ captures different classes, it can be partitioned into sets of instances belonging to specific classes \todo{cite our paper}). The idea here is to conceive $C(S)$ as a class (or more precisely, to employ $C(S)$ as an instance-based representation of a class). Due to the correspondence between elements $s \in S$ and $t \in C(S)$, the class of $t$ must correspond to the class of $s \in S$. A candidate $t \in C(S)$ is considered as a match only when it belongs to this class of interest. This is the case when $t$ shares the characteristics captured by $C(S)$, i.e. $t$ exhibits characteristics that are common to instances in $C(S)$. 

%For instance, sources instances $S$ are of the type Drug. Class-based matching exploits the intuition that correct matches in the target must belong to a class that corresponds to Drug, e.g. Medication. As a representation for the class of Medication, we use $C(S)$. Candidates that match $C(S)$ are inferred to be of the type Medication and thus, considered as matches. 

%During this process, $t$ is not compared with one single candidate but all candidates in $C(S)$. In fact, no information from the source is directly used, as for refinement, we actually compare every candidate in $C(S)$ with $C(S)$. That is, we do not perform direct matching between source and target but only use information in the target for further refinement. The scheme for this matching paradigm can be simply stated as $$sim(t, Class(s)) > \delta.$$  The main problems are how to obtain a representation of the class of interest, $Class(s)$, and what threshold to be used. 

%
%\begin{definition} Class-Based Matching - If set of source instances $S' \subset S$ has a $CTP$, and the target set $M$ has a $CTP$  where  $\forall s \in S'$, $\exists t \in M \land t \in C(s)$ then $t \in M$ forms a Same-as relation to $s \in S$
%\end{definition}
%
% In the next sections, we describe our solution for the direct matching and class-based matching 
%over heterogeneous data.






 